#ifndef _CFG_H_
#define _CFG_H_

#include "parser.h"
#include <map>
#include <set>
#include <stack>
#include <string>
#include <queue>

using namespace std;

class BasicBlock{
public:
	int in;//first line of the block, also can be seen as the id of the block
	int out;//last line of the block
	vector<int> preds;
	vector<int> succs;
	map<string, set<int> > definitions; //definitions that reach past this block from this block, maps variable name to line number.
	map<string, set<int> > predDefinitions; //incoming definitions from this block's predecessors that we might propagate
	map<string, set<int> > outDefinitions; //all definitions reaching out of this block;

	vector<set<string> > lives;
	vector<set<string> > defs;
	vector<set<string> > uses;

	//dominators
	set<int> dom;

	//dom tree
	int dt_parent;
	vector<int> dt_children;

	//dom frontier
	set<int> df;

	vector<Instr> phis;


	BasicBlock(int i, int o)
		:in(i), out(o), preds(), succs(), lives(), defs(), uses(), dom(), dt_parent(0), dt_children(), df(){
		set<string> s;
		lives.assign(out - in + 2, s);
		defs.assign(out - in + 1, s);
		uses.assign(out - in + 1, s);
	}

	set<string>& def(int idx){
		return defs[idx - in];
	}

	set<string>& use(int idx){
		return uses[idx - in];
	}

	set<string>& iLiveIn(int idx){
		return lives[idx - in];
	}

	set<string>& iLiveOut(int idx){
		return lives[idx - in + 1];
	}

	set<string>& bLiveIn(){
		return lives[0];
	}

	set<string>& bLiveOut(){
		return lives[out - in + 1];
	}

	void addPreds(int i);
	void addSuccs(int i);

	void resetLiveness();


};


class CFG{
public:
	vector<Instr>& is;
	map<int, BasicBlock *> nodes;//key: block id -- BasicBlock::in ; value: pointer to the block
	int entry;//entry of the function
	int end;//end of the function
	bool isMain;

	int dseInSCR;
	int dseOutSCR;
	vector<vector<int> > SCR; //Strongly connect regions for this function
	bool scr_found;
	int num_propagated;//number of constants propagated in this function
	int lines_moved;//number of lines moved with ssalicm;

	map<string, set<int> > var_def;

	CFG(vector<Instr>& instrs):is(instrs), nodes(), entry(0), end(0), isMain(false), SCR(1), scr_found(false), dseInSCR(0), dseOutSCR(0), num_propagated(0), lines_moved(0){}
	~CFG(){
		map<int, BasicBlock *>::iterator it;
		for(it = nodes.begin(); it != nodes.end(); it++){
			delete (*it).second;
		}
	}

	bool build(int start);
	void output(ostream& o);

	void findSCR();
	void printSCR(ostream& o);

	void scp();
	void printSCP(ostream& o);
	
	void liveness();
	bool dse();
	void printLiveness(ostream& o);
	void resetLiveness();

	void findDominators();
	void buildDomTree();
	void findDomFrontier(BasicBlock *);
	void printDomFrontier(ostream& o);

	void placePhi();
	void printVarDef(ostream& o);
	void printPhi(ostream& o);

	void rename();

	void ssacp(); //Single Static Assignment Constant Propagation
	bool ssalicm(int scr); //Single Static Assignment Loop Invarient Code Motion
	void printssalicm(ostream& o);

private:

	void findSCRhelper(set<int>& assigned, map<int, int>& ordering, int current, int& c, stack<int>& S, stack<int>& P, int& cur_scr);
	void findDefinitions();
	void reachingDefinitions(queue<BasicBlock*>& workList, set<int>& doneList);
	void propagate(int line, Instr* inst, map<string, set<int> >& curDefinitions, int& propagated, bool& changed);

	void initDefUse();
	bool isInSCR(int idx);

	void initVarDef();
	void renameHelper(BasicBlock * b, map<string, int>& c, map<string, stack<int> >& s);

	//ssalicm helpers
	bool canMove(int line, int scr);
	void doMove(const vector<int>& linestomove, int scr);
	bool inSCR(int line, int scr);
	bool definedInSCR(const Param& p, int scr);

};





#endif
